#include "game.h"
#include <random>
#include <algorithm>
#include <cassert>

std::vector<int> ans;
std::mt19937 rnd(0x20061013);
int c = 0;
int n;

int query(const std::vector<int>& v) {
	int r = count(v);
	for(int i = 0; i < n; ++i) r -= v[i] == ans[i];
	return r;
}

int len;

void solve(const std::vector<int>& v, int l, int r, int d, int cnt) {
	if(r - l + 1 <= len) {
		for(int i = l; i <= r; ++i) {
			if(ans[i-1]) continue;
			auto v0 = v;
			int p = i == 1 ? n : 1;
			std::swap(v0[i-1], v0[p-1]);
			if(query(v0) == 0) {
				++c;
				--cnt;
				ans[i-1] = v[i-1];
				if(cnt == 0) return;
			}
		}
		assert(0);
	}
	assert(cnt == 1);
	int mid = l + r >> 1;
	int t = 5;
	if(d <= 2) t = 10;
	bool ok = 1;
	std::vector<int> v0 = v;
	while(t-- && ok) {
		std::shuffle(v0.begin() + l - 1, v0.begin() + mid, rnd);
		if(query(v0) < cnt) ok = 0;
	}
	if(ok) { //right
		solve(v, mid + 1, r, d + 1, cnt);
	} else {
		solve(v, l, mid, d + 1, cnt);
	}
}

std::vector<int> guess(int n, int limit) {
	::n = n;
	if(n <= 4) {
		ans.resize(n);
		for(int i = 0; i < n; ++i) ans[i] = i + 1;
		do {
			if(count(ans) == n) return ans;
		} while(std::next_permutation(ans.begin(), ans.end()));
		assert(0);
		return ans;
	}
	len = n <= 100 ? 4 : 20;
	ans.resize(n);
	std::vector<int> qr(n);
	for(int i = 0; i < n; ++i) qr[i] = i + 1;
	while(c < n) {
		int cnt = 0;
		do {
			std::shuffle(qr.begin(), qr.end(), rnd);
		} while((cnt = query(qr)) != 1);
		solve(qr, 1, n, 0, cnt);
	}
	return ans;
}
